Binary Search Tree (BST) এর সাথে Binary Search গাইড ও নোট

Binary Search Tree (BST)

Binary Search Tree (BST) হলো একটি বিশেষ ধরনের বাইনারি ট্রি যেখানে প্রতিটি নোডের বাঁ পাশের চাইল্ড নোডগুলির মান (value) তার পিতার মানের থেকে ছোট এবং ডান পাশের চাইল্ড নোডগুলির মান তার পিতার মানের থেকে বড় থাকে। এই গুণের কারণে BST একটি স্বতন্ত্র ডাটা স্ট্রাকচার, যা ডেটা খোঁজার, ইনসার্ট এবং ডিলিট অপারেশনগুলোকে দ্রুততর করে তোলে।

BST এর বৈশিষ্ট্য:

1. Left Subtree: একটি নোডের বাম শাখায় থাকা সবগুলো নোড তার পিতার মানের থেকে ছোট।
2. Right Subtree: একটি নোডের ডান শাখায় থাকা সবগুলো নোড তার পিতার মানের থেকে বড়।
3. Unique Values: সাধারণত, BST এ প্রতিটি নোডের একটি ইউনিক মান থাকে।

Binary Search in a BST

Binary Search হল একটি অ্যালগরিদম যা একটি সজ্জিত অ্যারে বা ট্রিতে এলিমেন্ট খুঁজে বের করার জন্য ব্যবহৃত হয়। BST তে, এটি অ্যারে সিকোয়েন্সিংয়ের মতো কাজ করে, যেখানে আপনি ট্রির মধ্যে প্রতি স্টেপে আংশিকভাবে এলিমেন্ট অনুসন্ধান করেন, যতক্ষণ না সঠিক এলিমেন্ট পাওয়া যায়। BST এর এই বৈশিষ্ট্যটি আমাদের সহজেই একটি ভ্যালু খুঁজে পেতে সাহায্য করে।

BST অপারেশন

1. Insertion: BST তে একটি নতুন নোড ইনসার্ট করার জন্য, আপনি সঠিক পজিশনে ইনসার্ট করবেন, যা BST এর গুণাবলী বজায় রাখে।
2. Searching: BST তে একটি নির্দিষ্ট মান খোঁজার জন্য, আপনি প্রতিটি নোডে ভ্যালু চেক করবেন এবং ছোট হলে বাম শাখায়, বড় হলে ডান শাখায় যেতে থাকবেন।

BST এবং Binary Search ইমপ্লিমেন্টেশন

১. BST Node Definition

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

এখানে, Node ক্লাস একটি সাধারণ নোডের জন্য তৈরি করা হয়েছে, যেখানে data হল নোডের মান এবং left, right হলো তার বাম এবং ডান চাইল্ড নোড।

২. BST ইমপ্লিমেন্টেশন

public class BinarySearchTree {
    Node root;

    // Constructor
    public BinarySearchTree() {
        root = null;
    }

    // Insert a new node in the BST
    public void insert(int value) {
        root = insertRec(root, value);
    }

    // Helper function for insertion
    private Node insertRec(Node root, int value) {
        // If the tree is empty, return a new node
        if (root == null) {
            root = new Node(value);
            return root;
        }

        // Otherwise, recur down the tree
        if (value < root.data) {
            root.left = insertRec(root.left, value);
        } else if (value > root.data) {
            root.right = insertRec(root.right, value);
        }

        // return the (unchanged) node pointer
        return root;
    }

    // Search a value in the BST
    public boolean search(int value) {
        return searchRec(root, value);
    }

    // Helper function for searching
    private boolean searchRec(Node root, int value) {
        // Base case: root is null or value is present at the root
        if (root == null) {
            return false;
        }
        if (root.data == value) {
            return true;
        }

        // Value is greater than root's data, search in the right subtree
        if (value > root.data) {
            return searchRec(root.right, value);
        }

        // Value is smaller, search in the left subtree
        return searchRec(root.left, value);
    }

    // In-order traversal of the BST
    public void inorder() {
        inorderRec(root);
    }

    // Helper function for inorder traversal
    private void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }
}

৩. Main Method Example

public class Main {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        // Inserting values into the BST
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);

        // In-order traversal
        System.out.println("In-order traversal:");
        bst.inorder();  // Output should be sorted: 20 30 40 50 60 70 80
        System.out.println();

        // Searching for a value in the BST
        System.out.println("Search 40: " + bst.search(40));  // true
        System.out.println("Search 100: " + bst.search(100));  // false
    }
}

আউটপুট:

In-order traversal:
20 30 40 50 60 70 80 

Search 40: true
Search 100: false

৪. Binary Search Explanation in BST

BST তে Binary Search ব্যবহার করার সময় আপনি যা করেন তা হলো:

1. প্রথমে মূল নোড (root) থেকে শুরু করবেন।
2. যদি আপনি যে মানটি খুঁজছেন তা মূল নোডের মানের চেয়ে ছোট হয়, তবে আপনি বাম শাখায় চলে যাবেন।
3. যদি মানটি বড় হয়, তবে আপনি ডান শাখায় চলে যাবেন।
4. আপনি এইভাবে যতদিন না আপনি ডেটা খুঁজে পান বা একটি null নোডে পৌছাতে থাকবেন।

এই অ্যালগরিদমটি BST এর কাঠামোকে কাজে লাগিয়ে খুব দ্রুত কাজ করে, যেখানে গড় সময়ে সময় জটিলতা O(log n) হতে পারে, যেখানে n হলো নোডের সংখ্যা।

সারাংশ

Binary Search Tree (BST) একটি বাইনারি ট্রি যেখানে প্রতিটি নোডের বাম শাখায় থাকা মানগুলি তার পিতার চেয়ে ছোট এবং ডান শাখায় থাকা মানগুলি তার পিতার চেয়ে বড় থাকে। এটি Binary Search অপারেশন এর জন্য খুবই কার্যকরী, যেখানে দ্রুত ডেটা খোঁজা সম্ভব হয়। BST এর insert এবং search অপারেশনগুলো গড় সময়ে O(log n) এ সম্পন্ন হয়, যা এটি একটি শক্তিশালী ডাটা স্ট্রাকচার হিসেবে প্রতিষ্ঠিত করে।

এই ইমপ্লিমেন্টেশনটি:

• insert: একটি নতুন নোড ইনসার্ট করা।
• search: একটি নির্দিষ্ট মান খোঁজা।
• inorder traversal: সমস্ত মান সজ্জিত আকারে প্রিন্ট করা।

BST এবং Binary Search সমন্বয়ে একটি খুবই কার্যকরী এবং দক্ষ ডাটা স্ট্রাকচার তৈরী হয় যা স্ট্রিং, নাম্বার বা অন্যান্য অর্ডারড ডেটার জন্য উপযুক্ত।